package bag;

import java.util.Arrays;



class 零钱兑换_322_重做版 {
            public int coinChange(int[] coins, int amount) {
                // 背包问题总结https://leetcode-cn.com/problems/coin-change/solution/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-sq9n/
                int[] dp = new int[amount + 1]; // 组成 index元 最少需要的个数
                Arrays.fill(dp, amount + 1); // 硬币面额最小455是1  因此amount + 1是不可能的值
                dp[0] = 0;
                for(int j = 1; j <= amount; j++) { // 硬币面额最小是1 最多重复取 amount次
                    for(int i = 0; i< coins.length; i++) { // 逐个遍历硬币
                        if(j >= coins[i])
                        // 实际上是  （不取coins[i]）dp[i-1][j]  （取coins[i]）dp[i][j- coins[i]] + 1 取最小值  
                        dp[j] = Math.min(dp[j] , dp[j - coins[i]] + 1);  // 当前凑成j 需要的硬币数量  和再取一次当前硬币需要的硬币数量  取最小值
                    }
                }
                return dp[amount] == (amount + 1) ? -1 : dp[amount];
            }
        }
/**
 * 无关前i个   一维数组即可
 *  dp[i]  表示组成i需要的最小硬币个数
 * 状态转移方程 ：因为dp[i]  可能是加上任意一个数组中的硬币后得到
 *              因此遍历前面所有的硬币j   看减去该硬币面值后谁的需要的个数 最小
 *                 dp[i] = Min(dp[i - coin[j]] + 1 )
 */
public class 零钱兑换_322 {
    public int coinChange(int[] coins, int amount) {
        // 凑成j金额所需最小个数  注意提示条件 amount可能是 0
        int dp[] = new int[amount + 1];
        // 全是1块钱硬币的时候最大amount个  amount + 1 是不可能的最大值
        Arrays.fill(dp, amount + 1);
        // 组成0元最少需要0个
        dp[0] = 0;
        // 针对amount滚动
        for (int j = 1; j <= amount; j++) {
            for (int i = 1; i <= coins.length; i++) {
                //  凑齐j - coins[i-1]的 最小个数  求最小值
                if (j >= coins[i - 1]) {
                    dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
                }
                // j <  coins[i - 1] 时是不能要当前硬币的   因此 就等于不要当前硬币的dp[j] 的值dp[j] = dp[j] 不变化  所以不写
            }
        }

        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }


    public static void main(String[] args) {
        零钱兑换_322 a = new 零钱兑换_322();
        int i = a.coinChange(new int[]{1, 2, 5}, 11);
        System.out.println(i);
    }
}
